Whenever there is a flight flown between an origin and a destination, each leg of the flight requires the generation and filing of a flight plan. A flight plan is a document that lays out the ground route between the take-off and landing, the altitude levels to be flown and the speed schedule of the aircraft throughout the flight. The flight plan is used to compute the fuel required for the flight as well as the flight time.
Flight planning depends on a number of different factors. It is influenced by the upper air weather conditions such as winds, temperature and thunderstorm conditions. Another important factor affecting the flight planning process includes the aircraft performance with regard to the speeds allowable and the fuel efficiency of the aircraft under different altitude and speed conditions. Flight planning depends significantly on navigation data. Aircraft are typically constrained to fly along well defined airways and fixes, where fixes correspond to the nodes and the airways correspond to the arcs of a network.
The FAA (Federal Aviation Administration) also imposes restrictions on how to enter and exit airports as well as on the altitudes that can be flown by the aircraft. Over the domestic United States, aircraft are required to fly from east to west at certain altitudes and west to east at certain other altitudes. The revenue requirements of a flight also imposes payload constraints on the aircraft which determines the altitudes that can be flown by the aircraft.
The volume of flights handled daily by major airlines requires that the flight plan computation be very fast, to the order of 2 seconds for any domestic flight. This is a productivity constraint on the flight planning problem.
Flight planning is a mission critical process that starts with the estimation of the passenger and cargo payload for a flight. Flight plans are commonly generated by dispatchers two hours before the flight departure, and the proposed ground route for the flight is electronically sent to the FAA computer for approval. Approved flight plans are sent to the aircraft crew who review the plan and fuel the aircraft accordingly. If the conditions change for any reason, dispatchers have to generate new flight plans by performing a "what-if" analysis on the original flight plan.
Flight planning is at the heart of any real-time operations control to an airline. It is the primary activity that determines the airline operations and all other operational issues, such as irregular operations, flight cancellations, maintenance routing and gate planning, and ties in as peripheral activities to the flight planning process. Flight times are determined by flight planning, and the setting of airline schedules for the future is dependent on the distribution of flight times. Therefore, flight planning plays a key role in determining aircraft usage and designing the airline schedule timings for any leg of a flight. From a cost point of view, airline fuel costs can be as large as $1 billion per year at major airlines. Time costs related to missed connections and passenger goodwill lost due to late operations can be an even greater number in large airlines. Therefore, any savings in fuel and time can have a significant impact on the costs of running an airline.
The current flight planning methodology in operation for commercial airlines is a two step process. Each pair of departure and arrival cities has a set of a limited number of fixed routes. The first step is to roughly estimate the ground route from the fixed set of routes between any two departure and arrival points. This rough estimation is based upon choosing the fastest route by assigning approximate weather conditions along the route. For example, the initial portion of the route may consider lower altitude weather while later portions may consider higher altitudes for weather conditions. If there is a thunderstorm, the dispatcher has to visually see which routes avoid the thunderstorm and select the route that is most appropriate. The second step in current flight planning uses the rough estimate of the ground route to develop the altitude and speed schedule. The flight profiles for each altitude and mach number are developed to determine the best combination of altitudes and mach numbers that provides the lowest fuel and time costs. FIG. 1, discussed below, illustrates the steps involved in the existing conventional flight planning process.
The above approach to flight planning has a number of weaknesses and provides poor solutions to the problem of generating an optimal flight plan. The structure of the flight planning network which is composed of airways and fixes provides for literally millions of possible combinations in designing routes, and storing a set of a limited number of fixed routes is highly suboptimal. The wind patterns, which may vary widely on any given day, determine the best route and the set of fixed routes required to be used may comprise a very poor set of choices on a specific day. Furthermore, subdividing the process into separate steps of route selection followed by altitude and speed selection is also suboptimal because the route selection, altitude selection and speed selection are a tightly coupled phenomenon. Any decomposition of the process into route selection and then altitude and selection is fundamentally flawed and suboptimal. If a route is selected based upon approximate weather conditions at different altitudes, the actual flight profile may follow different altitudes due to payload and performance requirements of the aircraft. Therefore, the proposed flight plan may not turn out to be very good if compared with the initial assumption. The above methodology becomes worse if a thunderstorm is predicted. The dispatcher must visually select the routes that avoid a thunderstorm. This also leads to a poor selection of routes.
The FAA wants to reduce some of the navigation constraints by allowing direct links between fixes that are less than 260 nautical miles apart as part of the National Route Program. The use of such closely spaced fixes will increase the density of the National Route Program network. In a network of such increased density, a set of fixed routes is a very poor way to select the best flight plan.
The typical approach to flight plan optimization has been to consider it as a trajectory optimization problem from the physics of the aircraft motion. The problem is formulated as a continuous non-linear optimization problem. Such a formulation is solved using iterative search or calculus of variations to obtain a solution to the flight trajectory. This kind of formulation has some serious drawbacks. First of all, a four dimensional optimization over all altitudes, navigation locations and speed results in a very complex formulation. In addition, some of the important issues, such as the use of FAA defined altitudes, step climbs, climb of the aircraft, descent of the aircraft, and entry and exit to the airport, cannot be incorporated into one global optimization equation. Secondly, the iterative search or calculus of variations approach requires a high computation time and is therefore impractical for use in real time airline flight operations. One prior art reference entitled "Constrained Optimum Trajectories with Specified Range," explains some of the issues involved in trajectory optimization during long flights.
Another known approach to flight plan optimization has been to consider mathematical programming techniques such as dynamic programming. Most efforts in this area have been limited to free flight, which means the aircraft is unrestricted as far as navigation locations are considered on the ground and can fly pure lat/long flights. A grid of potential waypoints is constructed around a great circle route between the origin and the destination to develop an elliptical region of search. The potential waypoints are constructed so that their projections on the great circle route between the origin and the destination subdivides the great circle route into a number of stages. Thus, the structure of the problem gets transformed to a typical stage based dynamic programming problem. The problem is then solved using backward search by either decomposing the problem into a two-dimensional search over the location and a subsequent altitude profile search, or a combined four dimensional search over location, altitude and speed. The problem with this approach is the limitation to free flight, which is only relevant for some oceanic flights. Since commercial aircraft have to follow a network of airways and VOR/NDB fixes, this kind of a stage-based dynamic programming formulation is difficult to construct in real life.
Another problem is that the selection of an elliptical region around the great circle is a poor technique because the weather situation on any given day may make the entire elliptical region unfavorable. If there is a thunderstorm or a restricted airspace between an origin and a destination, an elliptical region may become impossible to construct. Moreover, if the problem is decomposed into location search and altitude search, the resulting flight plan is suboptimal because the location, altitude and speed of the aircraft are tightly coupled variables. Some known techniques employ the use of iteration in narrowing the elliptical region of search, but this makes the search slow and still remains an impractical way to solve the flight plan optimization problem.
There have also been some efforts at implementing recent advances in information technology for flight planning. One reference describes a commercial product being developed for meshing flight planning functions with real-time weather graphics. Another describes an expert system developed to support flight planning. However, these applications do not deal with the fundamental problem of developing an efficient, computationally robust optimization methodology that can be used for commercial flight planning functionality.
A need therefore exists for a system and method for generating minimum-cost airline flight plans in real time, where a large number of potential routes can be examined. The benefits from such a system and methodology include significant cost savings in fuel and time for an airline, and the ability to create a dynamic flight operations management system by integrating flight planning with other real time control issues in airline operations. Optimal flight planning enables an airline to better utilize its fleet of aircraft and allow more effective airline scheduling. Independent auditing has shown that the present invention may consistently save 3% on fuel and 1% on time for all flights using the National Route Program. The amount of savings is estimated at $30 Million per year.
The principal object of the present invention is to provide an innovative system and method for computing a minimum-cost airline flight plan in real time while satisfying the navigation, performance, weather, revenue and regulatory constraints for commercial airlines.
It is another object of the invention to provide a method for generating a minimum-cost airline flight plan that is capable of searching a large number of potential routes within an extremely fast computation time.
It is yet another object of the invention to provide a method for generating minimum-cost airline flight plans that may be incorporated into a dynamic flight operations management system.
It is still another object of the invention to provide a method for generating a minimum-cost airline flight plan that may be incorporated into a system for simulating airline operations to aid in the design and testing of airline schedules as well as in the performance of reliability analysis and payload analysis for the entire airline operations.